
#ifndef IHASHMAP_H
#define IHASHMAP_H

#include <BString>

using namespace BWE;

const int HASH_NULL = 0xffffffff;

template <class Value>
class IHashKey
{
	int m_uid;

public:
	IHashKey()
	{
		m_uid = 0;
	}
	IHashKey(int uid)
	{
		m_uid = uid;
	}

	int getUid1() const
	{
		return m_uid;
	}

	bool equals(const IHashKey<Value>& other) const
	{
		return getUid1() == other.getUid1();
	}

	inline BUInt getHash() const
	{
		BUInt key = m_uid;
		key += ~(key << 15);
		key ^= (key >> 10);
		key += (key << 3);
		key ^= (key >> 6);
		key += ~(key << 11);
		key ^= (key >> 16);
		return key;
	}
};

template <class Key, class Value>
class IHashMap
{
protected:
	BArray<int> m_hashTable;
	BArray<int> m_next;

	BArray<Value> m_valueArray;
	BArray<Key> m_keyArray;

	void growTables(const Key& key)
	{
		int newCapacity = m_valueArray.capacity();

		if (m_hashTable.size() < newCapacity)
		{
			int curHashtableSize = m_hashTable.size();

			m_hashTable.resize(newCapacity);
			m_next.resize(newCapacity);

			int i;

			for (i = 0; i < newCapacity; ++i)
			{
				m_hashTable[i] = HASH_NULL;
			}
			for (i = 0; i < newCapacity; ++i)
			{
				m_next[i] = HASH_NULL;
			}

			for (i = 0; i < curHashtableSize; i++)
			{
				int hashValue = m_keyArray[i].getHash() & (m_valueArray.capacity() - 1);
				m_next[i] = m_hashTable[hashValue];
				m_hashTable[hashValue] = i;
			}
		}
	}

public:
	void insert(const Key& key, const Value& value)
	{
		int hash = key.getHash() & (m_valueArray.capacity() - 1);
		int index = findIndex(key);
		if (index != HASH_NULL)
		{
			m_valueArray[index] = value;
			return;
		}

		int count = m_valueArray.size();
		int oldCapacity = m_valueArray.capacity();
		m_valueArray.append(value);
		m_keyArray.append(key);

		int newCapacity = m_valueArray.capacity();
		if (oldCapacity < newCapacity)
		{
			growTables(key);
			hash = key.getHash() & (m_valueArray.capacity() - 1);
		}
		m_next[count] = m_hashTable[hash];
		m_hashTable[hash] = count;
	}

	void remove(const Key& key)
	{
		int hash = key.getHash() & (m_valueArray.capacity() - 1);

		int pairIndex = findIndex(key);

		if (pairIndex == HASH_NULL)
		{
			return;
		}

		int index = m_hashTable[hash];

		int previous = HASH_NULL;
		while (index != pairIndex)
		{
			previous = index;
			index = m_next[index];
		}

		if (previous != HASH_NULL)
		{
			m_next[previous] = m_next[pairIndex];
		}
		else
		{
			m_hashTable[hash] = m_next[pairIndex];
		}

		int lastPairIndex = m_valueArray.size() - 1;

		if (lastPairIndex == pairIndex)
		{
			m_valueArray.pop_back();
			m_keyArray.pop_back();
			return;
		}

		int lastHash = m_keyArray[lastPairIndex].getHash() & (m_valueArray.capacity() - 1);

		index = m_hashTable[lastHash];
		previous = HASH_NULL;
		while (index != lastPairIndex)
		{
			previous = index;
			index = m_next[index];
		}

		if (previous != HASH_NULL)
		{
			m_next[previous] = m_next[lastPairIndex];
		}
		else
		{
			m_hashTable[lastHash] = m_next[lastPairIndex];
		}

		m_valueArray[pairIndex] = m_valueArray[lastPairIndex];
		m_keyArray[pairIndex] = m_keyArray[lastPairIndex];

		m_next[pairIndex] = m_hashTable[lastHash];
		m_hashTable[lastHash] = pairIndex;

		m_valueArray.pop_back();
		m_keyArray.pop_back();
	}

	int size() const
	{
		return m_valueArray.size();
	}

	const Value* getAtIndex(int index) const
	{
		if (index >= 0 && index < m_valueArray.size())
		{
			return &m_valueArray[index];
		}
		return 0;
	}

	Value* getAtIndex(int index)
	{
		if (index >= 0 && index < m_valueArray.size())
		{
			return &m_valueArray[index];
		}
		return 0;
	}

	Key getKeyAtIndex(int index)
	{
		return m_keyArray[index];
	}

	const Key getKeyAtIndex(int index) const
	{
		return m_keyArray[index];
	}

	Value* operator[](const Key& key)
	{
		return find(key);
	}

	const Value* operator[](const Key& key) const
	{
		return find(key);
	}

	const Value* find(const Key& key) const
	{
		int index = findIndex(key);
		if (index == HASH_NULL)
		{
			return NULL;
		}
		return &m_valueArray[index];
	}

	Value* find(const Key& key)
	{
		int index = findIndex(key);
		if (index == HASH_NULL)
		{
			return NULL;
		}
		return &m_valueArray[index];
	}

	int findIndex(const Key& key) const
	{
		BUInt hash = key.getHash() & (m_valueArray.capacity() - 1);
		if (hash >= (BUInt)m_hashTable.size())
		{
			return HASH_NULL;
		}
		int index = m_hashTable[hash];
		while ((index != HASH_NULL) && key.equals(m_keyArray[index]) == false)
		{
			index = m_next[index];
		}
		return index;
	}

	void clear()
	{
		m_hashTable.clear();
		m_next.clear();
		m_valueArray.clear();
		m_keyArray.clear();
	}
};

#endif
